<!DOCTYPE html>
<html lang="zh-CN">
    <head>
  <!-- 元数据 -->
  <meta charset="utf-8">
  <link rel="icon" href="">
  <title>priority | ALgarth's blog</title>
  <meta name="author" content="ALgarth" />
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="robots" content="index,follow" />
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <meta name="format-detection" content="telphone=no, email=no" />
  
    <meta name="keywords" content="priority_queue" />
  
  <meta name="description" content="Priority_queue的使用今天打算谈一谈priority_queue的使用，priority_queue声明在queue中，这部分内容跟queue有很多重合之处，因此即便是在c++圣经上也没有过多的描述 （The Cpp programming language 上只有一页的空间，可见其实内容都是从别人身上借的 ） 一. 一个例题的引入这个题初学贪心的时候其实都见到过 就是那个合并果子（洛">
<meta property="og:type" content="article">
<meta property="og:title" content="priority">
<meta property="og:url" content="http://algarth.github.io/2020/10/12/priority/index.html">
<meta property="og:site_name" content="ALgarth&#39;s blog">
<meta property="og:description" content="Priority_queue的使用今天打算谈一谈priority_queue的使用，priority_queue声明在queue中，这部分内容跟queue有很多重合之处，因此即便是在c++圣经上也没有过多的描述 （The Cpp programming language 上只有一页的空间，可见其实内容都是从别人身上借的 ） 一. 一个例题的引入这个题初学贪心的时候其实都见到过 就是那个合并果子（洛">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://algarth.github.io/null">
<meta property="article:published_time" content="2020-10-12T09:58:02.000Z">
<meta property="article:modified_time" content="2020-10-27T08:00:08.590Z">
<meta property="article:author" content="ALgarth">
<meta property="article:tag" content="priority_queue">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://algarth.github.io/null">
<meta name="twitter:site" content="@null">
  
  <!-- 站点验证相关 -->
  
    
    
    
  
  <!-- 样式表文件 -->
  <link rel="stylesheet" id="kratos-css" href="/css/kratosr.min.css" type="text/css" media="all">
  <link rel="stylesheet" id="highlight-css" href="/css/highlight.min.css" type="text/css" media="all">
  <link rel="stylesheet" id="fontawe-css" href="https://cdn.jsdelivr.net/npm/font-awesome@4.7.0/css/font-awesome.min.css" type="text/css" media="all">
  <link rel="stylesheet" id="nprogress-css" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" type="text/css" media="all">
  
  
  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">
  
  
    <link rel="stylesheet" id="darkmode-css" href="/css/kr-dark.min.css" type="text/css" media="all">
  
  <!-- 不得不预先加载的一些JS文件 -->
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
  
    <script src="https://cdn.jsdelivr.net/npm/qrcode_js@1.0.0/qrcode.min.js"></script>
  
  
<meta name="generator" content="Hexo 5.2.0"><link rel="alternate" href="/atom.xml" title="ALgarth's blog" type="application/atom+xml">
</head>


    <body class="custom-background">
        <div id="kratos-wrapper">
    <div id="kratos-page">
        <div id="kratos-header">
            <div class="nav-toggle"><a class="kratos-nav-toggle js-kratos-nav-toggle"><i></i></a></div>
            <header id="kratos-header-section">
                <div class="container">
                    <div class="nav-header">
                        <div class="color-logo"><a href="/">ALgarth&#39;s blog</a></div>
                        <nav id="kratos-menu-wrap">
                            <ul id="kratos-primary-menu" class="sf-menu">
                                
                                    
                                        <li><a href="/"><i class="fa fa-home"></i>首页</a></li>
                                    
                                
                                    
                                        <li><a href="/archives/"><i class="fa fa-file"></i>档案馆</a></li>
                                    
                                
                                    
                                        <li>
                                            <a><i class="fa fa-link"></i>链接</a>
                                            <ul class="sub-menu">
                                                
                                                    
                                                
                                                    
                                                        <li><a target="_blank" rel="noopener" href="https://blog.csdn.net/algarth">作者博客</a></li>
                                                    
                                                
                                                    
                                                        <li><a target="_blank" rel="noopener" href="https://github.com/ALgarth">项目链接</a></li>
                                                    
                                                
                                            </ul>
                                        </li>
                                    
                                
                            </ul>
                        </nav>
                    </div>
                </div>
            </header>
        </div>
        <div class="kratos-start kratos-hero-2">
            <!-- <div class="kratos-overlay"></div> -->
            <div class="kratos-cover kratos-cover-2 text-center">
                <div class="desc desc2 animate-box">
                    <a href="/">
                        <h2>ALgarth&#39;s blog</h2> <br />
                        <span>欢迎捞到摸鱼仙人的博客呢_(:3」∠)_</span>
                    </a>
                </div>
            </div>
        </div>

        <div id="kratos-blog-post">
            <div class="container">
                <div class="row">
                    
        <div id="main">
            <section class="col-md-8">
    <article>
        <div class="kratos-hentry kratos-post-inner clearfix">
            <header class="kratos-entry-header">
                <h1 class="kratos-entry-title text-center">priority</h1>
                
                <div class="kratos-post-meta text-center">
                    <span>
                        <i class="fa fa-calendar"></i> 2020-10-12
                        <i class="fa fa-folder"></i> 分类于 
                        <i class="fa fa-user"></i> 作者 ALgarth
                        <i class="fa fa-edit"></i> 
                        
                        
                            ~3.42K
                        
                        字
                        
                    </span>
                </div>
            </header>
            <div class="kratos-post-content">
                
                    <div class="kratos-post-inner-toc">
                        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#Priority-queue%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="toc-number">1.</span> <span class="toc-text">Priority_queue的使用</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80-%E4%B8%80%E4%B8%AA%E4%BE%8B%E9%A2%98%E7%9A%84%E5%BC%95%E5%85%A5"><span class="toc-number">1.1.</span> <span class="toc-text">一. 一个例题的引入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="toc-number">1.2.</span> <span class="toc-text">题目描述</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C-priority%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="toc-number">1.3.</span> <span class="toc-text">二. priority的使用</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%BB%98%E8%AE%A4%E7%9A%84%E5%A4%A7%E6%A0%B9%E5%A0%86"><span class="toc-number">1.3.1.</span> <span class="toc-text">默认的大根堆</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B0%8F%E6%A0%B9%E5%A0%86"><span class="toc-number">1.3.2.</span> <span class="toc-text">小根堆</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#pair%E7%9A%84%E9%BB%98%E8%AE%A4"><span class="toc-number">1.3.3.</span> <span class="toc-text">pair的默认</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#cmp%E5%86%99%E6%B3%95%E5%92%8C%E9%87%8D%E8%BD%BD%E5%86%99%E6%B3%95"><span class="toc-number">1.3.4.</span> <span class="toc-text">cmp写法和重载写法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E7%9A%84%E8%A7%A3%E7%AD%94"><span class="toc-number">1.4.</span> <span class="toc-text">题目的解答</span></a></li></ol></li></ol>
                    </div>
                
                <hr />
                <h1 id="Priority-queue的使用"><a href="#Priority-queue的使用" class="headerlink" title="Priority_queue的使用"></a>Priority_queue的使用</h1><p>今天打算谈一谈priority_queue的使用，priority_queue声明在queue中，这部分内容跟queue有很多重合之处，因此即便是在c++圣经上也没有过多的描述</p>
<p><del>（The Cpp programming language 上只有一页的空间，可见其实内容都是从别人身上借的 ）</del></p>
<h2 id="一-一个例题的引入"><a href="#一-一个例题的引入" class="headerlink" title="一. 一个例题的引入"></a>一. 一个例题的引入</h2><p>这个题初学贪心的时候其实都见到过</p>
<p>就是那个<strong>合并果子</strong>（洛谷1090 USACO06NOV）</p>
<p>这个题可以说是贪心的经典例题了其实</p>
<blockquote>
<h2 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h2><p>在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。</p>
<p>每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1n-1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。</p>
<p>因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 111 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。</p>
<p>例如有 333 种果子，数目依次为 111 ， 222 ， 999 。可以先将 111 、 222 堆合并，新堆数目为 333 ，耗费体力为 333 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 121212 ，耗费体力为 121212 。所以多多总共耗费体力 =3+12=15=3+12=15=3+12=15 。可以证明 151515 为最小的体力耗费值。</p>
</blockquote>
<p>不想看的话我口头描述了，给定一个数组，每次选择两项进行相加，代价是两者的和，怎样合并使得最后合并为1个元素而且代价最小</p>
<p><del>（先回顾口诀：不开long long见祖宗）</del></p>
<p>其实很好办倒是，每次合并最小的两个就是了，如果直接排序前缀和了，可能会出现像是10，20，25，26…之类的情况，两者加起来反而结果不是最小的了，（有没有感觉像是最小生成树？），总之要给出一种解决的办法，使得每次都是最小的两个合并</p>
<p>如果每次都进行排序，快排nlogn，快排n的整数次，复杂度直接飙升到n^2longn，这个题n的范围还是1e5，n^2都不行，你怎么办？</p>
<p>其实正常而言，这时就得拿出堆排序了，索性你又不想写20行的堆或者根本不会写，那这时就要拿出priority_queue大法了</p>
<h2 id="二-priority的使用"><a href="#二-priority的使用" class="headerlink" title="二. priority的使用"></a>二. priority的使用</h2><p>上文阐述了为何使用，那这部分就要提怎么使用了。priority_queue和queue差不太多，因此有下面几个操作</p>
<h3 id="默认的大根堆"><a href="#默认的大根堆" class="headerlink" title="默认的大根堆"></a>默认的大根堆</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt; //priority_queue同样是定义在这个头文件之下的</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	ios::sync_with_stdio(<span class="number">0</span>);</span><br><span class="line">	<span class="built_in">priority_queue</span>&lt;<span class="keyword">int</span>&gt; q1;</span><br><span class="line">	<span class="comment">//直接创建的话是默认使用大根堆，就是大的在前 </span></span><br><span class="line">	q1.push(<span class="number">1</span>);</span><br><span class="line">	q1.push(<span class="number">2</span>);</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;q1.top(); <span class="comment">//输出结果为2</span></span><br><span class="line">    q1.pop(); <span class="comment">//弹出首元</span></span><br><span class="line">    <span class="built_in">cout</span>&lt;&lt;q1.top(); <span class="comment">//结果为1</span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>像这样可以基本使用了优先队列了，优先队列和队列的差别就在于他会对内部的元素进行排序，这种排序的复杂度其实还是在圣经上描述的好，摘抄如下</p>
<blockquote>
<p>保持元素顺序并不是免费的，但也不一定有很高的代价，prioirity_queue的一种很有效的实现方法是使用一个树结构来追踪元素的相对位置，这种方法保证push和pop都是logn的，priority_queue可以几乎肯定是由heap实现的</p>
</blockquote>
<p>这也就是他的时间复杂度，每次都会进行堆排序，时间复杂度应该是nlogn的，刚好可以满足我们对这个题的要求</p>
<p>当然还有一点没有考虑，如何写其他的排序方法：</p>
<p>其实考虑到sort的两种写法，这里其实也有两种写法，甚至还有几种给定的和默认的写法</p>
<h3 id="小根堆"><a href="#小根堆" class="headerlink" title="小根堆"></a>小根堆</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	ios::sync_with_stdio(<span class="number">0</span>);</span><br><span class="line">	<span class="built_in">priority_queue</span>&lt;<span class="keyword">int</span>,<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;,greater&lt;<span class="keyword">int</span>&gt; &gt; q1;</span><br><span class="line">	<span class="comment">//这样手动选择小根堆</span></span><br><span class="line">	<span class="comment">//这里的vector是表示传入的数据保存方法，可以使用vector也可以deque，不支持list </span></span><br><span class="line">	<span class="comment">//后面的greater&lt;int&gt;就是排序方法 </span></span><br><span class="line">	q1.push(<span class="number">1</span>);</span><br><span class="line">	q1.push(<span class="number">2</span>);</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;q1.top(); <span class="comment">//输出结果为1 </span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="pair的默认"><a href="#pair的默认" class="headerlink" title="pair的默认"></a>pair的默认</h3><p>pair默认是进行返回first从小到大（对刚好和大根堆认知相反了），如果相等，返回second从小到大，代码不贴了</p>
<h3 id="cmp写法和重载写法"><a href="#cmp写法和重载写法" class="headerlink" title="cmp写法和重载写法"></a>cmp写法和重载写法</h3><p>不贴代码了，其实和sort的写法一模一样，重载&lt;运算符，而且cmp写的位置刚好就在尖括号的最后一个位置（原先的greater&lt; int &gt;）位置</p>
<h2 id="题目的解答"><a href="#题目的解答" class="headerlink" title="题目的解答"></a>题目的解答</h2><p>这个题解其实就显而易见了，我还是先把我的烂代码发一遍吧</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> asd cout&lt;&lt;<span class="meta-string">&quot; SB &quot;</span>&lt;&lt;endl; </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned long long </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f </span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    ios::sync_with_stdio(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">int</span> n;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">    ll sum=<span class="number">0</span>;</span><br><span class="line">    <span class="built_in">priority_queue</span>&lt;ll,<span class="built_in">vector</span>&lt;ll&gt;,greater&lt;ll&gt; &gt; q;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;++i)&#123;</span><br><span class="line">    	ll num;</span><br><span class="line">    	<span class="built_in">cin</span>&gt;&gt;num;</span><br><span class="line">		q.push(num);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> temp=q.top();</span><br><span class="line">	q.pop();</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n<span class="number">-1</span>;++i)&#123;</span><br><span class="line">		<span class="keyword">int</span> t=q.top();</span><br><span class="line">		q.pop();</span><br><span class="line">		sum+=temp+t;</span><br><span class="line">		q.push(temp+t);</span><br><span class="line">		temp=q.top();</span><br><span class="line">		q.pop();</span><br><span class="line">	&#125;</span><br><span class="line">    <span class="built_in">cout</span>&lt;&lt;sum;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>内容就不解释了，其实我觉得讲到这步田地其实代码自己就能写了</p>
<p>当然其实我还想说的是</p>
<p>洛谷题解里有个时间之神，O（n）过得</p>
<p>所以说说O（n）的思路</p>
<p>首先懂得都懂，要是两者相加，产生的新位数可能会比排序好的第三个元素大对吧</p>
<p>所以干脆就开两个队列，一个储存原数组，一个储存加后的出的结果</p>
<p>两个都从小到大排序的<del>（先不要想排序的时间复杂度）</del></p>
<p>每次从两个队列的头上找出两个最小的元素，加起来，结果加到最后的输出结果sum里，和推到第二个结果数组里</p>
<p>是不是很美，直接O（n）了</p>
<p>我们再来考虑一下排序的时间</p>
<p>后面的排序其实就是第二个队列的排序，这个队列直接push_back推入其实就不用排序对吧，每次最小的相加，肯定后面出来的结果比前面的要大对吧</p>
<p>那初始的排序怎么最优呢？</p>
<p>这就拿出置换之神——桶排序</p>
<p><del>只要我桶开的够大，MLE就追不上我！！</del></p>
<p>总之就这样，全O（n）了</p>
<p>我直接%%%</p>
<hr>
<p><em>我是ALgarth，如果有缘，我们下次再见。</em></p>
<p><em>图片来自网络，侵删。</em></p>
<p><em>本人拙笔草见，如果内容有误，请及时联系修改</em></p>

            </div>
            
                <div class="kratos-copyright text-center clearfix">
                    <h5>本作品采用 <a rel="license nofollow" target="_blank" href="http://creativecommons.org/licenses/by-sa/4.0/">知识共享署名-相同方式共享 4.0 国际许可协议</a> 进行许可</h5>
                </div>
            
            <footer class="kratos-entry-footer clearfix">
                
                    <div class="post-like-donate text-center clearfix" id="post-like-donate">
                    
                        <a class="donate" href="javascript:;"><i class="fa fa-bitcoin"></i> 打赏</a>
                    
                    
                        <a class="share" href="javascript:;"><i class="fa fa-share-alt"></i> 分享</a>
                        <div class="share-wrap" style="display: none;">
    <div class="share-group">
        <a href="javascript:;" class="share-plain qq" onclick="share('qq');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-qq"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain qzone" onclick="share('qzone');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-star"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weixin pop style-plain" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weixin"></i>
            </div>
            <div class="share-int">
                <div class="qrcode" id="wechat-qr"></div>
                <p>打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮</p>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weibo" onclick="share('weibo');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weibo"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain facebook style-plain" onclick="share('facebook');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-facebook"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain twitter style-plain" onclick="share('twitter');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-twitter"></i>
            </div>
        </a>
    </div>
    <script type="text/javascript">
        $(()=>{
            new QRCode("wechat-qr", {
                text: "http://algarth.github.io/2020/10/12/priority/",
                width: 150,
                height: 150,
                correctLevel : QRCode.CorrectLevel.H
            });
        });
        function share(dest) {
            const qqBase        = "https://connect.qq.com/widget/shareqq/index.html?";
            const weiboBase     = "https://service.weibo.com/share/share.php?";
            const qzoneBase     = "https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?";
            const facebookBase  = "https://www.facebook.com/sharer/sharer.php?";
            const twitterBase   = "https://twitter.com/intent/tweet?";
            const hostUrl       = "http://algarth.github.io/2020/10/12/priority/";
            const title         = "「priority」";
            const excerpt       = `Priority_queue的使用今天打算谈一谈priority_queue的使用，priority_queue声明在queue中，这部分内容跟queue有很多重合之处，因此即便是在c++圣经上也没有过多的描述
（The Cpp pr...`;
            let _URL;
            switch (dest) {
                case "qq"       : _URL = qqBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";     break;
                case "weibo"    : _URL = weiboBase+"url="+hostUrl+"&title="+title+excerpt;                                 break;
                case "qzone"    : _URL = qzoneBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";  break;
                case "facebook" : _URL = facebookBase+"u="+hostUrl;                                                        break;
                case "twitter"  : _URL = twitterBase+"text="+title+excerpt+"&url="+hostUrl;                                break;
            }
            window.open(_URL);
        };
    </script>
</div>
                    
                    </div>
                
                <div class="footer-tag clearfix">
                    <div class="pull-left">
                    <i class="fa fa-tags"></i>
                        <a class="tag-none-link" href="/tags/priority-queue/" rel="tag">priority_queue</a>
                    </div>
                    <div class="pull-date">
                    <span>最后编辑：2020-10-27</span>
                    </div>
                </div>
            </footer>
        </div>
        
            <nav class="navigation post-navigation clearfix" role="navigation">
                
                <div class="nav-previous clearfix">
                    <a title=" c++primary（下部）" href="/2020/10/11/c-primary-1/">&lt; 上一篇</a>
                </div>
                
                
                <div class="nav-next clearfix">
                    <a title=" 计算机组成原理笔记（第一章）" href="/2020/10/13/organization/">下一篇 &gt;</a>
                </div>
                
            </nav>
        
        
    </article>
</section>
        </div>
                
            <section id="kratos-widget-area" class="col-md-4 hidden-xs hidden-sm">
                
                    <aside id="krw-about" class="widget widget-kratos-about clearfix">
    
    <div class="photo-background"></div>
    <div class="photo-wrapper clearfix">
        <div class="photo-wrapper-tip text-center">
            <img class="about-photo" src="/images/avatar.webp" />
        </div>
    </div>
    <div class="textwidget">
        
            <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#Priority-queue%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="toc-number">1.</span> <span class="toc-text">Priority_queue的使用</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80-%E4%B8%80%E4%B8%AA%E4%BE%8B%E9%A2%98%E7%9A%84%E5%BC%95%E5%85%A5"><span class="toc-number">1.1.</span> <span class="toc-text">一. 一个例题的引入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="toc-number">1.2.</span> <span class="toc-text">题目描述</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C-priority%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="toc-number">1.3.</span> <span class="toc-text">二. priority的使用</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%BB%98%E8%AE%A4%E7%9A%84%E5%A4%A7%E6%A0%B9%E5%A0%86"><span class="toc-number">1.3.1.</span> <span class="toc-text">默认的大根堆</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B0%8F%E6%A0%B9%E5%A0%86"><span class="toc-number">1.3.2.</span> <span class="toc-text">小根堆</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#pair%E7%9A%84%E9%BB%98%E8%AE%A4"><span class="toc-number">1.3.3.</span> <span class="toc-text">pair的默认</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#cmp%E5%86%99%E6%B3%95%E5%92%8C%E9%87%8D%E8%BD%BD%E5%86%99%E6%B3%95"><span class="toc-number">1.3.4.</span> <span class="toc-text">cmp写法和重载写法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E7%9A%84%E8%A7%A3%E7%AD%94"><span class="toc-number">1.4.</span> <span class="toc-text">题目的解答</span></a></li></ol></li></ol>
        
    </div>
</aside>
                
                    <!-- Moved to about.ejs -->
                
                    

                
                    
  <aside id="krw-tags" class="widget widget-kratos-tags clearfix">
    <h4 class="widget-title"><i class="fa fa-tags"></i>标签聚合</h4>
      <div class="tag-clouds">
        <a href="/tags/OS/" style="font-size: 0.6em;">OS</a> <a href="/tags/c-%E4%BB%8E%E5%85%A5%E9%97%A8%E5%88%B0%E4%B8%8D%E5%85%A5%E9%97%A8/" style="font-size: 0.7em;">c++从入门到不入门</a> <a href="/tags/priority-queue/" style="font-size: 0.6em;">priority_queue</a> <a href="/tags/projectpool/" style="font-size: 0.6em;">projectpool</a> <a href="/tags/tmp/" style="font-size: 0.6em;">tmp</a> <a href="/tags/trailer/" style="font-size: 0.7em;">trailer</a> <a href="/tags/update/" style="font-size: 0.6em;">update</a> <a href="/tags/%E5%89%8D%E8%A8%80/" style="font-size: 0.6em;">前言</a> <a href="/tags/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/" style="font-size: 0.8em;">计算机组成原理</a> <a href="/tags/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E6%B1%87%E6%80%BB/" style="font-size: 0.6em;">计算机组成原理汇总</a> <a href="/tags/%E8%AE%A1%E7%BD%91/" style="font-size: 0.6em;">计网</a>
      </div>
  </aside>

                
                    
  <aside id="krw-posts" class="widget widget-kratos-poststab">
  <h4 class="widget-title"><i class="fa fa-file"></i>最新文章</h4>
  <div class="tab-content">
      <ul class="list-group">
        
        
          
          
            <a class="list-group-item" href="/2021/12/23/tmp/"><i class="fa  fa-book"></i> 小范围开源期末材料</a>
            
          
        
          
          
            <a class="list-group-item" href="/2021/10/30/OS/"><i class="fa  fa-book"></i> OS第一章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2021/10/23/cnet/"><i class="fa  fa-book"></i> 计网第一章</a>
            
          
        
          
          
        
          
          
            <a class="list-group-item" href="/2021/10/19/projectpool/"><i class="fa  fa-book"></i> 计划进程池设定</a>
            
          
        
          
          
        
          
          
            <a class="list-group-item" href="/2020/12/31/organization-ex/"><i class="fa  fa-book"></i> 计算机组成原理汇总篇</a>
            
          
        
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
      </ul>
  </div>
  </aside>

                
            </section>
        
        </div>
    </div>
</div>
<footer>
    <div id="footer">
        <div class="kr-tool text-center">
            <div class="tool">
                
                    <div class="box search-box">
                        <a href="/search/">
                            <span class="fa fa-search"></span>
                        </a>
                    </div>
                
                
                    <div class="box theme-box" id="darkmode-switch">
                        <span class="fa fa-adjust"></span>
                    </div>
                
                
            </div>
            <div class="box gotop-box">
                <span class="fa fa-chevron-up"></span>
            </div>
        </div>
        <div class="container">
            <div class="row">
                <div class="col-md-6 col-md-offset-3 footer-list text-center">
                    <ul class="kratos-social-icons">
                        
                        <li><a href="mailto:algarth@163.com"><i class="fa fa-envelope"></i></a></li>
                        
                        
                        
                        
                        
                        <li><a target="_blank" rel="nofollow" href="https://github.com/ALgarth"><i class="fa fa-github"></i></a></li>
                        
                    </ul>
                    <ul class="kratos-copyright">
                        <div>
                            <li>&copy; 2022 ALgarth 版权所有.</li>
                            <li>本站已运行<span id="span_dt">Loading...</span></li>
                        </div>
                        <div>
                            <li>Theme <a href="https://github.com/Candinya/Kratos-Rebirth" target="_blank">Kratos:Rebirth</a></li>
                            <li>Made with&nbsp;<i class="fa fa-heart throb" style="color:#d43f57"></i>&nbsp;by <a href="https://candinya.com" target="_blank" rel="nofollow">Candinya</a>.</li>
                        </div>
                        <div>
                            <li>Powered by <a href="https://hexo.io" target="_blank" rel="nofollow">Hexo</a></li>
                            <li>Hosted on <a href="https://github.io" target="_blank">Github Pages</a></li>
                        </div>
                        <div>
                            
                            
                        </div>
                    </ul>
                </div>
            </div>
        </div>
    </div>
</footer>
</div>
</div>

        <script defer src="https://cdn.jsdelivr.net/npm/bootstrap@3.3.4/dist/js/bootstrap.min.js"></script>
<script defer src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.js"></script>
<script>const notMobile = (!(navigator.userAgent.match(/(phone|pad|pod|iPhone|iPod|ios|iPad|Android|Mobile|BlackBerry|IEMobile|MQQBrowser|JUC|Fennec|wOSBrowser|BrowserNG|WebOS|Symbian|Windows Phone)/i)));</script>

    <div>
        <canvas id="snow"></canvas>
        <script async type="text/javascript" src="/js/snow.min.js"></script>
    </div>

<script async src="/js/candy.min.js"></script>


    <script defer src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>

<script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js"></script>
<script defer src="/js/kratosr.min.js"></script>
<script defer src="/js/pjax.min.js"></script>

    <script defer src="https://cdn.jsdelivr.net/npm/layui-src@2.5.5/dist/layui.all.js"></script>


    <script defer src="/js/kr-dark.min.js"></script>


    </body>
</html>